#include <stdio.h>
#include<stdlib.h>
typedef int  BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode*left;
    struct BinaryTreeNode*right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode *newnode=(BTNode*)malloc(sizeof(BTNode));
    newnode->data=x;
    newnode->right=NULL;
    newnode->left=NULL;
    return  newnode;
}
BTNode* CreatBinaryTree()
{
    BTNode*node1= BuyNode(1);
    BTNode*node2=BuyNode(2);
    BTNode*node3=BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}

int BinaryTreeSize(BTNode* root)//二插树节点的个数
{
    //分治法
    if(root==NULL)//节点为空时
        return 0;
   return 1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);
}
int BinaryTreeLeafSize(BTNode* root)//二叉树叶子节点的个树
{
    if(root==NULL)
        return 0;
   if(root->left==NULL&&root->right==NULL)//判断的条件
       return 1;
   return BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);//递归
}

int BinaryTreeLevelKSize(BTNode* root, int k)//二叉树有k层有多少个节点
{
    if(root==NULL)//节点位空停止递归
        return 0;
    if(k==1)//到那层停止递归
       return 1;
    return BinaryTreeLevelKSize(root->left,k-1)+BinaryTreeLevelKSize(root->right,k-1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//二叉树中是否有这个节点
{
    if(root==NULL)
        return NULL;
     if(root->data==x)
      return root;

    BTNode* TreeLeft =BinaryTreeFind(root->left,x);
    BTNode* TreeRight =BinaryTreeFind(root->right,x);
    if(TreeLeft)
    {
        return TreeLeft;
    }


   return TreeRight;
}

int main()
{

    BTNode* ret= CreatBinaryTree();

    int sz=0;

   sz= BinaryTreeSize(ret);
   printf("%d\n",sz);

    sz=BinaryTreeLeafSize(ret);
    printf("%d\n",sz);

    sz=BinaryTreeLevelKSize(ret,4);
    printf("%d\n",sz);


    BTNode*Pret= BinaryTreeFind(ret,4);
    if(ret==NULL)
    {
        printf("此树没有这个节点");
    }
    else
    {
        printf("找到了节点为->");
        printf("%d",*Pret);

    }




}
